package problems;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

import com.google.common.collect.HashMultimap;
import com.google.common.collect.HashMultiset;
import com.google.common.collect.Multimap;
import com.google.common.collect.Multiset;

public class Euler062 extends AbstractEuler {

	private static Map<Multiset<String>, Integer> counts = new HashMap<Multiset<String>, Integer>();
	private static Multimap<Multiset<String>, Long> roots = HashMultimap.create();
	
	private static final int REQUIRED_PERMUTATIONS = 5;
	
	
	@Override
	public Number calculate() {
		for (int powerOfTen = 1; powerOfTen < 20; powerOfTen++) {
			
			List<Multiset<String>> possibleResults = new ArrayList<Multiset<String>>();
			
			for (long i = (long) Math.pow(10, powerOfTen - 1); i < Math.pow(10, powerOfTen); i++) { //first try 1^3 through 9^3, then 10^3 through 99^3, etc.
				long cube = i * i * i;
				String[] digits = String.valueOf(cube).split("(?<=\\G.{1})");
				Multiset<String> digitSet = HashMultiset.create(Arrays.asList(digits));
				
				if (counts.containsKey(digitSet)) {
					counts.put(digitSet, counts.get(digitSet) + 1);
					System.out.println("adding cube " + cube + " to existing set " + roots.get(digitSet));
				} else {
					counts.put(digitSet, 1);
					System.out.println("new cube: " + cube);
				}
				
				roots.put(digitSet, i);
				
				int cubicPermutations = counts.get(digitSet);			
				if (cubicPermutations == REQUIRED_PERMUTATIONS) {
					possibleResults.add(digitSet); //only a possible result, because we might find another permutation in this iteration
				} 
			}
			
			if (possibleResults.size() > 0) {
				
				List<Multiset<String>> definiteResults = new ArrayList<Multiset<String>>();
				
				for (Multiset<String> digitSet : possibleResults) {
					if (counts.get(digitSet) == REQUIRED_PERMUTATIONS) {
						definiteResults.add(digitSet);
					}
				}
				
				if (definiteResults.size() > 0) {
					List<Long> cubeRootsOfAllPermutations = new ArrayList<Long>();
					for (Multiset<String> digitSet : definiteResults) {
						cubeRootsOfAllPermutations.addAll(roots.get(digitSet));
					}
					Collections.sort(cubeRootsOfAllPermutations);
					Long smallestCubeRoot = cubeRootsOfAllPermutations.get(0);
					Long smallestCube = smallestCubeRoot * smallestCubeRoot * smallestCubeRoot;
					return smallestCube;
				}
				
			}
			
		}
		
		throw new RuntimeException("no cubes with exactly " + REQUIRED_PERMUTATIONS + " cube permutations found within first 10^20 perfect cubes");
		
	}

	@Override
	protected Number getCorrectAnswer() {
		return 127035954683L;
	}


}
